Prior to setting forth a short discussion of the related art, it may be helpful to set forth definitions of certain terms that will be used hereinafter.
The term “Open Systems Interconnection model” (OSI Model) refers herein to a conceptual model that characterizes and standardizes the communication functions of a telecommunication or computing system without regard of their underlying internal structure and technology. Its goal is the interoperability of diverse communication systems with standard protocols. The model partitions a communication system into abstraction layers. The original version of the model defined seven layers. As referred herein, L7 denotes Applications Layer; L6 denotes Presentation Layer L5 denotes Session Layer; L4 denotes Transport Layer; L3 denotes Network Layer; L2 denotes Link Layer; and L1 denotes Physical Layer.
The term “middlebox” refers herein to a computer networking device that transforms, inspects, filters, or otherwise manipulates traffic for purposes other than packet forwarding. Common examples of middleboxes include firewalls which filter unwanted or malicious traffic, and network address translators, which modify packets' source and destination addresses. Dedicated middlebox hardware is widely deployed in enterprise networks to improve network security and performance; however, even home network routers often have integrated firewall, NAT, or other middlebox functionality.
The term “Deep Packet Inspection” (DPI), also called “complete packet inspection” and “Information eXtraction” (IX) refers herein to a form of computer network packet filtering that examines the data part (and possibly also the header) of a packet as it passes an inspection point, searching for protocol non-compliance, viruses, spam, intrusions, or defined criteria to decide whether the packet may pass or if it needs to be routed to a different destination, or, for the purpose of collecting statistical information.
The term “Software-defined networking” (SDN) refers herein to an approach in computer networking that allows network administrators to manage network services through abstraction of lower-level functionality. This is done by decoupling the system that makes decisions about where traffic is sent (the control plane) from the underlying systems that forward traffic to the selected destination (the data plane).
In contemporary networks, middleboxes play a major role as often forwarding packets is not enough to meet operators demands and other functionalities (such as security, QoS/QoE provisioning, and load balancing) are required. Traffic is usually routed through a sequence of such middleboxes, which either reside across the network or in a single, consolidated location. Although middleboxes provide a vast range of capabilities, there are components that are shared among many of them.
A prime example that is common to almost all middleboxes that deal with L7 protocols is Deep Packet Inspection (DPI). Today, traffic is inspected from scratch by all the middleboxes on its route.
Over the last few years, a great effort was invested in redesigning middleboxes' architecture. In traditional networks, middleboxes are placed at strategic places along the traffic path, which are determined by the network topology; traffic is going through the middleboxes as dictated by the regular routing mechanism. SDN makes it possible to perform traffic steering, where routing through a chain of middleboxes is determined using a middlebox-specific routing considerations that might differ significantly from traditional routing schemes.
Recently, telecommunication vendors launched the Network Functions Virtualization (NFV) initiative that aims to virtualize network appliances at the operator. The main objective of NFV is to reduce the operational costs of these appliances (which are traditionally implemented in middleboxes) by obtaining the same functionality in software that runs on commodity servers. NFV provides an easier management and maintenance by eliminating the need to deal with multiple hardware types and vendors; moreover, as NFV is implemented in software, it promotes innovation in this domain DPI is the most significant example of an appliance or functionality that may be virtualized. Moreover, as most suggestions for NFV operate in a distributed private cloud, leveraging traffic repetitions for high-speed DPI will be very beneficial due to the locality in the traffic at different vantage points at the operator.
There are several pioneer works about middlebox virtualization. One example provides a mechanism to place a middlebox, such as the Bro NIDS, in a virtual environment, where the virtual machine (VM) might migrate between different machines. Another example deals with standardization of a unified control to middleboxes, inspired by the SDN paradigm. Nevertheless, virtualizing middleboxes raises several issues that should be carefully dealt with, such as efficient fault tolerance, availability, and management.
A different approach to tackle the problem raised by managing multiple middleboxes is to offer a consolidated solution consisting of a single hardware that consolidates multiple middleboxes.
To reduce the high equipment and operating costs of middleboxes, there were several suggestions to outsource the middlebox functionalities as a service received by an entity outside the network.
It is noted that while DPI is a significant component in many middleboxes, those which focus on L4-L2 lower layers (e.g., NAT or L3 Load Balancer) are not using it, as they work only on the packet header rather than its payload.
As SDN in general include header rewriting, there is a trend to move such tasks from dedicated middleboxes to the SDN data plane and implement more sophisticated functionality as an application at the SDN controller. Most L7 middleboxes, on the other hand, use DPI to some extent.
DPI lies at the core of many middlebox applications (see Table 1), and is based on pattern matching, in which the payload of the packet is compared against a predetermined Middlebox DPI signatures.
TABLE 1MiddleboxDPI signaturesExampleIntrusion DetectionMalicious activitySNORT,SystemBROAnti-Virus/SPAMMalicious activity ClamAVL7 FirewallMalicious activityLinux L7-filter,ModSecurityL7 Load BalancingApps/URLsF5, A10Leakage PreventionLeakage activityCheck Point DLPSystemNetwork AnalyticInterestingQosmosinformationTraffic ShaperApplicationsBlue Coat,PacketShapper
String matching is an essential building block of most contemporary DPI engines. In many implementations, even if most patterns are regular expressions, string matching is performed first (namely, as a pre-filter) and it consists of most of the work performed by the engine. Specifically, Snort extracts the strings that appeared in the regular expressions (called anchors). Then, string matching is performed over these anchors, and if all anchors originating from a specific regular expression are matched, then a regular expression matching of the corresponding expression is performed.
This is a common procedure since regular expression engines work inefficiently on a large number of expressions. Specifically, there are two common solutions to represent regular expressions: a Deterministic Finite Automata (DFA) or Nondeterministic Finite Automata (NFA). The DFA suffers from memory explosion especially when combining a few expressions into one data structure, while the NFA suffers from a large penalty in time.
As for (multiple) string matching, the classic algorithms are of Aho-Corasick and Wu-Manber, where the Aho-Corasick (AC) algorithm is the de-facto standard for contemporary network intrusion detection systems (NIDS). It matches multiple strings simultaneously by first constructing a DFA that represents the signatures set; then, with this DFA on its disposal, the algorithm scans the text in a single pass.
Specifically, the DFA construction is done in two phases. First, a tree of the strings is built, where strings are added one by one from the root as chains (each node in the tree corresponds to a DFA state). When signatures share a common prefix, they also share the corresponding set of states in the tree. The edges of the first phase are called forward transitions. In the second phase, additional edges deal with situations where, given an input symbol b and a state s, there is no forward transition from s using b. Let the label of a state s, denoted by L(s), be the concatenation of symbols along the path (of forward transition) from the root to s. Furthermore, let the depth of a state s be the length of the label L(s).
The transition from s given symbol b is to a state s0, whose label L(s0) is the longest suffix of L(s)b among all other DFA states. For example, FIG. 2 depicts a DFA 200 that was constructed for signatures set {E,BE,BD,BCD,BCAA,CDBCAB}.
The DFA is traversed starting from the root. Traversing to an accepting state indicates that some signatures are a suffix of the input; one of these signatures always corresponds to the label of the accepting state. The correctness of the AC algorithm essentially stems from the following simple property:
Property 1
                Let b1, . . . , bn be the input, and let s0, . . . , sn be the sequence of states the AC algorithm goes through, after scanning the symbols one by one (s0 is the root of the DFA).        For any i 2 {1, . . . , n}, L(si) is a suffix of b1, . . . , bi; furthermore, it is the longest such suffix among all other states of the DFA.        
The most common approach to store the DFA in memory is as a full-table AC, whose rows correspond to states and columns to symbols. Cell (i, j) holds the next state given that the current state is si and the symbol is bj. This approach is fast (under normal traffic) since only one read-operation is required for each input byte. Albeit, its memory footprint is large, leading to several memory representations that trade time with memory.
There is an extensive research on accelerating the DPI process, both in hardware and in software. Most software-based solutions accelerate the DPI process by optimizing its underlying data structure (namely, its DFA).